- Murmur2
-
MurmurHash2 — простая и быстрая хэш-функция общего назначения, разработанная Остинон Апплеби. Не является криптографически-безопасной, возвращает 32-разрядное беззнаковое число.
Из достоинств функции авторами отмечена простота, хорошее распределение, мощный лавинный эффект, высокая скорость и сравнительно высокая устойчивость к коллизиям. Текущие версии алгоритма оптимизированы под Intel-совместимые процессоры.
Содержание
Пример кода
unsigned int MurmurHash2 ( char * key, unsigned int len) { const unsigned int m = 0x5bd1e995; const unsigned int seed = 0; const int r = 24; unsigned int h = seed ^ len; const unsigned char * data = (const unsigned char *)key; while (len >= 4) { unsigned int k; k = data[0]; k |= data[1] << 8; k |= data[2] << 16; k |= data[3] << 24; k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; data += 4; len -= 4; } switch (len) { case 3: h ^= data[2] << 16; case 2: h ^= data[1] << 8; case 1: h ^= data[0]; h *= m; }; h ^= h >> 13; h *= m; h ^= h >> 15; return h; }
MurmurHash 2A
Вторая версия хэш-функции имеет некоторые недостатки. В частности, это проблема коллизий на небольших строках. Исправленный вариант имеет структуру типа Merkle-Damgard, выполняется немного медленнее (примерно на 20 %), но показывает лучшую статистику.
#define mmix(h,k) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; } unsigned int MurmurHash2A ( const void * key, int len, unsigned int seed ) { const unsigned int m = 0x5bd1e995; const int r = 24; unsigned int l = len; const unsigned char * data = (const unsigned char *)key; unsigned int h = seed; while(len >= 4) { unsigned int k = *(unsigned int*)data; mmix(h,k); data += 4; len -= 4; } unsigned int t = 0; switch(len) { case 3: t ^= data[2] << 16; case 2: t ^= data[1] << 8; case 1: t ^= data[0]; }; mmix(h,t); mmix(h,l); h ^= h >> 13; h *= m; h ^= h >> 15; return h; }
MurmurHash2 — коллизии
Коллизии для алгоритма MurmurHash2 для текста в кодировке cp866:
30f0fa9f: ПО-АВГУСТОВСКИ ПРОЛЕПЕТАЛА
3128688e: DEADSORBIMENTO ОБРАЩЕННОМУ
Ссылки
- Хэш-функции общего назначения
- Исходные тексты хэш-функий общего назначения
- Страничка функции
- Статистика коллизий MurmurHash и ее модификация
- Статистика производительности популярных хэш-функций
Хеш-функции Общего назначения Криптографические JH • HAVAL • Keccak • LM-хеш • MD2 • MD4 • MD5 • MD6 • N-Hash • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 • SHA-1 • SHA-2 • Skein • Snefru • Tiger • Whirlpool • ГОСТ Р 34.11-94
Категория:- Хеш-функции
Wikimedia Foundation. 2010.